/*
 * @lc app=leetcode.cn id=433 lang=cpp
 * @lcpr version=30204
 *
 * [433] 最小基因变化
 */


// @lcpr-template-start
using namespace std;
#include <algorithm>
#include <array>
#include <bitset>
#include <climits>
#include <deque>
#include <functional>
#include <iostream>
#include <list>
#include <queue>
#include <stack>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
// @lcpr-template-end
// @lc code=start
class Solution {
public:
    int minMutation(string startGene, string endGene, vector<string>& bank) {
       // 将基因库转为集合，提高查询效率
       unordered_set<string> bankSet(bank.begin(), bank.end());
        
       // 如果目标基因不在基因库中，直接返回-1
       if (bankSet.find(endGene) == bankSet.end()) {
           return -1;
       }
       
       // 可能的基因字符
       vector<char> genes = {'A', 'C', 'G', 'T'};
       
       // BFS队列：存储当前基因和当前突变次数
       queue<pair<string, int>> q;
       q.push({startGene, 0});
       
       // 已访问集合，避免重复访问
       unordered_set<string> visited;
       visited.insert(startGene);
       
       while (!q.empty()) {
           auto [current, steps] = q.front();
           q.pop();
           
           // 如果找到目标基因，返回当前步数
           if (current == endGene) {
               return steps;
           }
           
           // 尝试改变每个位置的字符
           for (int i = 0; i < current.size(); ++i) {
               char original = current[i];
               // 尝试每种可能的基因字符
               for (char g : genes) {
                   if (g == original) continue; // 跳过相同的字符，无需突变
                   
                   current[i] = g; // 进行突变
                   
                   // 如果突变后的基因在基因库中且未访问过
                   if (bankSet.count(current) && !visited.count(current)) {
                       visited.insert(current);
                       q.push({current, steps + 1});
                   }
               }
               current[i] = original; // 恢复原字符，尝试下一个位置
           }
       }
       
       // 无法到达目标基因
       return -1;
    }
};
// @lc code=end



/*
// @lcpr case=start
// "AACCGGTT"\n"AACCGGTA"\n["AACCGGTA"]\n
// @lcpr case=end

// @lcpr case=start
// "AACCGGTT"\n"AAACGGTA"\n["AACCGGTA","AACCGCTA","AAACGGTA"]\n
// @lcpr case=end

// @lcpr case=start
// "AAAAACCC"\n"AACCCCCC"\n["AAAACCCC","AAACCCCC","AACCCCCC"]\n
// @lcpr case=end

 */

